home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / std / c / 715 < prev    next >
Encoding:
Text File  |  1996-08-06  |  2.2 KB  |  49 lines
  1. Newsgroups: comp.std.c
  2. Path: in1.uu.net!jyacc!usenet
  3. From: jtrigg@marks.jyacc.com (Jim Trigg)
  4. Subject: Re: Restrictions on qsort compare function?
  5. In-Reply-To: pcurran@inforamp.net's message of Mon, 08 Apr 1996 17:14:13 GMT
  6. X-Nntp-Posting-Host: marks
  7. Message-ID: <9livf9cusp.fsf@marks.jyacc.com>
  8. Sender: jtrigg@marks.jyacc.com
  9. Organization: JYACC, Inc. 
  10. X-Newsreader: Gnus v5.1
  11. References: <4iokop$h4p@lyra.csx.cam.ac.uk> <4iqjar$2m9@usenet.pa.dec.com>
  12.     <4jgltp$f9l@lyra.csx.cam.ac.uk> <828644274snz@genesis.demon.co.uk>
  13.     <4k28t4$2g0@sam.inforamp.net> <828726582snz@genesis.demon.co.uk>
  14.     <4k69bf$ehg@sam.inforamp.net> <828971813snz@genesis.demon.co.uk>
  15.     <4kbl1l$74r@sam.inforamp.net>
  16. Date: Tue, 9 Apr 1996 14:54:14 GMT
  17.  
  18. In article <4kbl1l$74r@sam.inforamp.net> pcurran@inforamp.net (Peter
  19. Curran) writes:
  20.  
  21. > On Mon, 08 Apr 96 13:56:53 GMT in article
  22. >     <828971813snz@genesis.demon.co.uk> Lawrence Kirby
  23. >     <fred@genesis.demon.co.uk> (Lawrence Kirby) wrote:
  24.  
  25. >>> IMHO, qsort() is required to return an array that is sorted
  26. >>> according to the criteria implied by the comparison function.
  27. >>> That is, at the point where qsort returns, the array must match
  28. >>> the order implied by the comparison function.
  29.  
  30. > The comparison function I postulated *is* consistent, at any instant
  31. > in time.  (Just to be clear - another correspondent suggested my
  32. > original posting may not have said quite what I intended.  The
  33. > comparison function I suggested., or intended, calculates as result
  34. > by comparison of the values pointed at by the parameters, in a way
  35. > we can all agree is acceptable.  However, it then calls time(), and
  36. > if the result it odd it negates the result before returning it.  In
  37. > a conventional implementation of time(), it reverses the order every
  38. > second, but defines a consistent order at any given time.)
  39.  
  40. So what happens if the array is large enough that qsort takes longer
  41. than a second to complete?  The return values from the comparison
  42. function are no longer consistent.  Is the compiler vendor then
  43. obligated to produce an implementation of qsort that will complete a
  44. sort in a constant amount of time?  That is what breaks your
  45. comparison function.
  46.  
  47. Just a Thought,
  48. Jim Trigg
  49.